package com.lw.leetcode.node;

import com.lw.leetcode.node.Node;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**133. 克隆图
 * @Author liw
 * @Date 2021/4/29 13:42
 * @Version 1.0
 */
public class CloneGraph {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Node n = new Node(node.val);
        Map<Integer, Node> map = new HashMap<>(128, 1);
        Map<Integer, Integer> map2 = new HashMap<>(128, 1);
        find(node, n, map);
        find2(node, n, map, map2);
        return n;
    }

    private static void  find(Node node, Node copy, Map<Integer, Node> map) {
        List<Node> neighbors = node.neighbors;
        if (neighbors != null) {
            List<Node> newList = new ArrayList<>(neighbors.size());
            for (Node neighbor : neighbors) {
                int val = neighbor.val;
                Node n = map.get(val);
                if (n == null) {
                    n = new Node(val);
                    map.put(val, n);
                    find(neighbor, n, map);
                }
                newList.add(n);
            }
            copy.neighbors = newList;
        }
    }

    private static void  find2(Node node, Node copy, Map<Integer, Node> map, Map<Integer, Integer> map2) {
        if (map2.get(copy.val) != null) {
            return;
        }
        List<Node> neighbors = node.neighbors;
        if (neighbors != null) {
            List<Node> newList = new ArrayList<>(neighbors.size());
            for (Node neighbor : neighbors) {
                int val = neighbor.val;
                Node n = map.get(val);
                newList.add(n);
            }
            copy.neighbors = newList;
            map2.put(copy.val, 1);

            int size = neighbors.size();
            for (int i = 0; i < size; i++) {
                find2(neighbors.get(i), newList.get(i), map, map2);
            }
        }

    }
}
